package com.caoyanan.algorithm.question.zuoTraining.training004.class03;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * 经典水王问题
 *
 * 给定一个数组arr，如果有某个数出现次数超过了数组长度的一半，打印这个数，如果没有不打印
 *
 * 给定一个数组arr和整数k，arr长度为N，如果有某些数出现次数超过了N/K，打印这些数，如果没有不打印
 * @author: caoyanan
 * @time: 2021/6/19 18:50
 */
public class Question03_FindAppearManyTimesNumber {

    public static void main(String[] args) {

        int[] arr = { 1, 2, 3, 1, 1, 2, 1 };
        int number = findAppearHalfTimesNumber(arr);
        System.out.println("超过一半的次数是 " + number);
        int k = 4;
        Integer[] answer = findAppearMoreThanNDivideK(arr, k);
        System.out.printf("超过 %s 次数的是 %s \n", answer.length / k, Arrays.toString(answer));
    }

    /**
     * 核心一点：超过 n/k 个次数，那么最多有 (k-1)个候选
     * 同样准备一个lastNumber,和count
     * 但此时可能有(k-1)个数，所以需要一个map，且如果遇到一个不同的数，直接删除k-1个
     * @param arr
     * @param k
     * @return
     */
    private static Integer[] findAppearMoreThanNDivideK(int[] arr, int k) {
        Map<Integer, Integer> lastNumber = new HashMap<>(k-1);

        for (int i = 0; i < arr.length; i++) {
            if (lastNumber.containsKey(arr[i])) {
                lastNumber.put(arr[i], lastNumber.get(arr[i])+1);
            } else if (lastNumber.size() < k - 1) {
                lastNumber.put(arr[i], 1);
            } else {
                List<Integer> removeList = new LinkedList<Integer>();
                for (Map.Entry<Integer, Integer> set : lastNumber.entrySet()) {
                    Integer key = set.getKey();
                    Integer value = set.getValue();
                    if (value == 1) {
                        removeList.add(key);
                    }
                    lastNumber.put(key, value - 1);
                }
                for (Integer removeKey : removeList) {
                    lastNumber.remove(removeKey);
                }
            }
        }

        List<Integer> numbers = lastNumber.entrySet()
                .stream()
                .filter(it -> it.getValue() > (arr.length / k))
                .map(Map.Entry::getKey)
                .collect(Collectors.toList());
        return numbers.toArray(new Integer[]{});
    }

    /**
     * 找出出现次数一半以上的数字
     * 准备两个变量，lastNumber 和 count
     * 如果count=0,直接记录当前数字到lastNumber
     * 如果遇到的数字与lastNumber相同，count++，
     * 遇到的数字与lastNumber不同，count--
     * 最后剩余的数字，就是出现一半以上的数字
     * @param arr
     * @return
     */
    private static int findAppearHalfTimesNumber(int[] arr) {

        int lastNumber = 0;
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (count == 0) {
                lastNumber = arr[i];
            } else if (arr[i] == lastNumber) {
                count ++;
            } else {
                count --;
            }
        }
        count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == lastNumber) {
                count++;
            }
        }
        if (count > (arr.length / 2)) {
            return lastNumber;
        }
        return Integer.MIN_VALUE;
    }
}
